package 链表;

import lombok.AllArgsConstructor;
import lombok.Data;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class No430扁平化多级双向链表 {

    /**
     * 多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
     *
     * 给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
     * 输出：[1,2,3,7,8,11,12,9,10,4,5,6]
     * 解释：...
     * 总之:这题还是去看官方题目的的那个图,就是让子链子拼接到自己的后面,然后子链子最后连上之前的next
     */
    @AllArgsConstructor
    class Node {

        public int val;
        public Node prev;
        public Node next;
        public Node child;

    }

    public Node flatten(Node head) {

        if (head == null) return null;

        Node pseudoHead = new Node(0, null, head, null);

        Node prev = pseudoHead;
        Node curr ;

        Stack<Node> stack = new Stack<>();

        stack.push(head);

        while (!stack.isEmpty()) {

            //本次节点
            curr = stack.pop();

            //前驱连接本次
            prev.next = curr;

            //本次连接前驱
            curr.prev = prev;

            /**
             * 一定是先遍历完孩子,然后再遍历完next
             */
            //下一个不为null,就塞进下一个
            if (curr.next != null)
                stack.push(curr.next);

            //孩子节点不为null,就塞进下一个
            if (curr.child != null) {
                stack.push(curr.child);
                //删除子节点(及时维护,题意不要子节点)
                curr.child = null;
            }
            //前驱=本次
            prev = curr;
        }
        //分离虚拟节点
        pseudoHead.next.prev = null;

        return pseudoHead.next;

    }


    public static void main(String[] args) {

        long round = Math.round(-11.5);
        System.out.println(round);

    }

}